
class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """

        if s == "":
            return ""


        window = dict()
        need = dict()
        for c in t:
            need.setdefault(c, 0)
            need[c] += 1

        l, r = 0, 0
        valid = 0 
        res = None
        while r < len(s):
            c = s[r]

            r += 1

            if need.get(c, 0) > 0 :
                window[c] = window.get(c, 0) + 1
                if window[c] == need[c]:
                    valid += 1
            
            while valid == len(need):
                # 更新最小覆盖子串
                if res == None or r - l < len(res):
                    res = s[l:r]
                
                d = s[l]
                l += 1
                if need.get(d, 0) > 0:
                    if  window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return res
                    
            
if __name__ == '__main__':
    s = Solution()
    ins = "ADOBECODEBANC"
    t = "ABC"
    res = s.minWindow(ins, t)
    print(res)